package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2022-01-09 18:10
 **/
public class LeetCode2130 {

    //寻找中点+反转链表
    public int pairSum(ListNode head) {
        //伪头结点
        ListNode tou = new ListNode();
        tou.next = head;
        ListNode first = head;
        //second会到达中点,且前半部分会反转,second成为了前半部分的头结点
        ListNode second = tou;
        //前驱结点
        ListNode pre = null;

        //快慢指针寻找中点同时反转前半部分链表
        do {
            first = first.next.next;
            ListNode next = second.next;
            //如果当前second是伪头结点则无需反转
            if (second != tou) {
                second.next = pre;
                pre = second;
            }
            second = next;
        } while (first != null && first.next != null);

        //经过快慢指针的遍历,此时second已经指向中点(奇数就是中间的那个,偶数则是靠左边的那个),pre最后指向second的前一个节点
        //此时中点还未反转,我们先获取它正常的next节点,即右半边的头结点
        ListNode head2 = second.next;
        //再将前半部分的中点反转指向它的前一个节点,此时second就是前半部分的头结点,例如(1->2->3->4) 最后就是(pre)1 <- 2(second)和 (head2)3 -> 4
        second.next = pre;

        int max = 0;
        //分别向前后遍历,找到孪生节点的最大值
        while (second != null) {
            max = Math.max(max, head2.val + second.val);
            second = second.next;
            head2 = head2.next;
        }
        return max;
    }

    //集合
    /*public int pairSum(ListNode head) {
        List<Integer> list = new ArrayList<>();
        ListNode temp = head;
        while (temp != null) {
            list.add(temp.val);
            temp = temp.next;
        }

        int n = list.size();
        int max = 0;
        for (int i = 0; i <= (n / 2) - 1; ++i) {
            max = Math.max(list.get(i) + list.get(n - i - 1), max);
        }

        return max;
    }*/


}
